package com.hao.leetcode;

public class Demo14 {
    public static void main(String[] args) {
        Demo14 demo = new Demo14();
        // 示例 1:
        //
        // 输入: ["flower","flow","flight"]
        //输出: "fl"
        String[] strs = new String[]{"flower", "flow", "flight"};
        String s1 = demo.longestCommonPrefix(strs);
        System.out.println(s1);
        // 示例 2:
        //
        // 输入: ["dog","racecar","car"]
        //输出: ""
        //解释: 输入不存在公共前缀。
        strs = new String[]{"dog", "racecar", "car"};
        String s2 = demo.longestCommonPrefix(strs);
        System.out.println(s2);

        strs = new String[]{"c", "c"};
        String s3 = demo.longestCommonPrefix(strs);
        System.out.println(s3);
        System.out.println("c".startsWith("c"));
    }

    //第一种解法
    public String longestCommonPrefix(String[] strs) {
        String s = "";
        if (strs.length == 0) {
            return s;
        }

        if (strs.length == 1) {
            return strs[0];
        }

        String sMin = strs[0];

        //找出最短的那个字符串
        for (int i = 0; i < strs.length; i++) {
            if (sMin.length() > strs[i].length()) {
                sMin = strs[i];
            }
        }

        //
        boolean flag = true;
        for (int i = 1; i <= sMin.length(); i++) {
            String pre = sMin.substring(0, i);
            for (int j = 0; j < strs.length; j++) {
                String t = strs[j];
                if (!t.startsWith(pre)) {
                    flag = false;
                }
            }
            if (!flag) {
                s = sMin.substring(0, i - 1);
                break;
            }
        }
        if (flag) {
            s = sMin;
        }
        return s;
    }

    //第二种解法
    public String longestCommonPrefix2(String[] strs) {
        if (strs.length == 0) {
            return "";
        }
        String s = strs[0];
        for (int i = 1; i < strs.length; i++) {
            int len = s.length() < strs[i].length() ? s.length() : strs[i].length();
            s = s.substring(0, len);
            String tem = strs[i];
            for (int j = 0; j < len; j++) {
                if (s.charAt(j) != tem.charAt(j)) {
                    if (j == 0)
                        return "";
                    else {
                        s = s.substring(0, j);
                        break;
                    }
                }
            }
        }
        return s;
    }
}
